/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    /*
   dfs() 计算一个结点的最大贡献值
    空节点的最大贡献值等于 0。
    非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和
    对于叶节点而言，最大贡献值等于节点值；
    */
    int dfs(TreeNode* root)
    {
        if(!root) return 0;
        int left=max(0,dfs(root->left));
        int right=max(0,dfs(root->right));
        ans=max(ans,root->val+left+right);
        return root->val+max(left,right);
    }
    private:
        int ans;
    public:
    int maxPathSum(TreeNode* root) {
        // write code here
        ans=INT_MIN;
        dfs(root);
        return ans;
    }
};